//Cracking coding interview, 17.8
//find max sum of an array
//3:18PM--3:32PM--3:43PM(bug free)

#include<iostream>
#include<deque>
using namespace std;

int MaxSubSum(int *ar, int n, deque<int>& subarr) {
	if(n<0) return -1;
	if(n==0) return 0;
	if(n==1) {
		if(ar[0]>0) {
			subarr.push_back(ar[0]);
			return ar[0];
		} else {
			return 0;
		}
	}

	int All=0;
	int Local=0;
	deque<int> localstr;
	subarr.clear();
	for(int i=0; i<n; i++) {
		if(Local>=0) {
			localstr.push_back(ar[i]);
		} else {
			localstr.clear();
			localstr.push_back(ar[i]);
		}
		Local=max(ar[i], Local+ar[i]);
		if(All<Local) {
			subarr=localstr;
		}
		All=max(All, Local);
	}
	return All;
}

int main(int argc, char *argv[]) {
	int a[]={2, -8, 3, -2, 4, -10};
	deque<int> subarr;
	int n=MaxSubSum(a, 6, subarr);
	return 0;
}